package _07_串;

import java.util.Stack;

public class _32_最长有效括号 {

    public static void main(String[] args) {
        String str = "";
        System.out.println(longestValidParentheses(str));
    }

    public static int longestValidParentheses(String s) {
        if (s.length() == 0 || s.length() == 1) return 0;
        char[] chars = s.toCharArray();
        Stack<Integer> stack = new Stack<>();
        int[] flags = new int[chars.length];
        for (int i = 0; i < chars.length; i++) {
            // 左括号入栈
            if (chars[i] == '(') {
                stack.push(i);
            } else {
                if (stack.isEmpty()) flags[i] = 1;
                else stack.pop();
            }
        }
        // 未匹配的括号则是不合法的
        while (!stack.isEmpty()) {
            flags[stack.pop()] = 1;
        }

        // 求解连续0的最长序列
        int len = 0;
        int max = 0;
        for (int flag : flags) {
            if (flag == 1) {
                len = 0;
                continue;
            }
            len++;
            max = Math.max(max, len);
        }
        return max;
    }

    // 动态规划
    public static int longestValidParentheses2(String s) {
        if (s.length() == 0 || s.length() == 1) return 0;
        char[] chars = s.toCharArray();
        // 令前i个元素为有效括号长度个数
        int[] dp = new int[s.length()];
        int max = 0;
        for (int i = 1; i < chars.length; i++) {
            // 如果最后2个字符为 ((，者可以判断其为无效括号，情况为0
            if (chars[i] == ')') {
                if (chars[i - 1] == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && chars[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                max = Math.max(dp[i], max);
            }
        }
        return max;
    }

    // 动态规划
    public static int longestValidParentheses1(String s) {
        if (s.length() == 0 || s.length() == 1) return 0;
        char[] chars = s.toCharArray();
        // 令前i个元素为有效括号长度个数
        int[] dp = new int[s.length()];
        int max = 0;
        for (int i = 1; i < chars.length; i++) {
            if (chars[i] == ')') {
                if (chars[i - 1] == '(') {
                    // 直接匹配 最后2个括号()
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && chars[i - dp[i - 1] - 1] == '(') {
                    // 最后两个括号))
                    dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                max = Math.max(dp[i], max);
            }
        }
        return max;
    }

}
